#pragma once
#include <vector>
#include <stack>
#include <string>
#include <cassert>

using namespace std;


enum UNIT_TYPE
{
	UNIT_TYPE_DIGIT = 0,
	UNIT_TYPE_OPER,
};
struct unit
{
	UNIT_TYPE type;
	int data;
};

typedef vector<unit> ElementList;

ElementList SpliteExpr(string expr)
{
	ElementList list;

	bool bScanDigit = false;
	int d = 0;
	for (int i = 0; i < expr.size(); i++)
	{
		unit u;
		char c = expr[i];
		if (c >= '0' && c <= '9')
		{
			if (!bScanDigit)
			{
				bScanDigit = true;
				d = 0;
			} 
			d = d * 10 + c - '0';
		}
		else
		{
			if (bScanDigit)
			{
				bScanDigit = false;
				u.type = UNIT_TYPE_DIGIT;
				u.data = d;
				list.push_back(u);
			}
			
			switch (c)
			{
			case '+':
			case '-':
			case '*':
			case '/':
			case '(':
			case ')':
				u.type = UNIT_TYPE_OPER;
				u.data = c;
				list.push_back(u);
				break;
			default:
				break;
			}
		}	
	}

	if (bScanDigit)
	{
		unit u;
		u.type = UNIT_TYPE_DIGIT;
		u.data = d;
		list.push_back(u);
	}

	return list;
}

int GetOperPri(char oper)
{
	if (oper == '+' || oper == '-')
	{
		return 1;
	}
	else if (oper == '*' || oper == '/')
	{
		return 2;
	}
	else if (oper == '(' || oper == ')')
	{
		return 3;
	}
	else
	{
		assert(false);
	}

	return -1;
}

int Calc(char op, int n1, int n2)
{
	switch (op)
	{
	case '+':
		return n1 + n2;
		break;
	case '-':
		return n1 - n2;
		break;
	case '*':
		return n1 * n2;
		break;
	case '/':
		return n1 / n2;
		break;
	default:
		assert(false);
		break;
	}

	return 0;
}

int CalcExpr(string expr)
{
	stack<char> oper;
	stack<int> digit;

	ElementList e = SpliteExpr(expr);

	// calc
	for (int i = 0; i < e.size(); )
	{
		const unit& u = e[i];
		if (u.type == UNIT_TYPE_DIGIT)
		{
			digit.push(u.data);
			i++;
		}
		else if (u.type == UNIT_TYPE_OPER)
		{
			if (oper.empty())
			{
				oper.push(u.data);
				i++;
			}
			else
			{
				if (u.data == ')')
				{
					while (oper.top() != '(')
					{
						char op = oper.top();
						oper.pop();

						int n2 = digit.top();
						digit.pop();

						int n1 = digit.top();
						digit.pop();

						digit.push(Calc(op, n1, n2));
					}
					oper.pop();
					i++;
				}
				else if (u.data == '(')
				{
					oper.push(u.data);
					i++;
				}
				else
				{
					int curPri = GetOperPri(u.data);
					int topPri = GetOperPri(oper.top());
					if (curPri > topPri)
					{
						int n1 = digit.top();
						digit.pop();

						digit.push(Calc(u.data, n1, e[i + 1].data));
						i += 2;
					}
					else
					{
						oper.push(u.data);
						i++;
					}
				}
			}
		}
	}

	while (!oper.empty())
	{
		char op = oper.top();
		oper.pop();

		int n2 = digit.top();
		digit.pop();

		int n1 = digit.top();
		digit.pop();

		digit.push(Calc(op, n1, n2));
	}

	return digit.top();
}
